#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	int minJumps(vector<int>& arr)
	{
		unordered_map<int, vector<int>> val2idx;
		int length = size(arr);
		vector minDis(length, INT_MAX);
		for (int i = 0; i < length; i++) val2idx[arr[i]].emplace_back(i);
		queue<int> que { { 0 } };
		minDis[0] = 0;

		auto func = [&, length](int idx, int cval) {
			if (idx < 0 || idx == length || minDis[idx] != INT_MAX) return;
			minDis[idx] = cval + 1;
			que.emplace(idx);
		};
		array dval = { -1, 1 };

		while (!que.empty()) {
			int cidx = que.front(); que.pop();
			int cdis = minDis[cidx];
			for (int d : dval) func(d + cidx, cdis);
			auto&& idxs = val2idx[arr[cidx]];
			for (int i = 0, len = size(idxs); i < len; i++) func(idxs[i], cdis);
			idxs.clear();
		}
		int res = minDis[length - 1];
		return res == INT_MAX ? -1 : res;
	}

private:
	template <typename T>
	void quick_remove_at(vector<T>& vec, size_t idx)
	{
		vec[idx] = move(vec.back());
		vec.pop_back();
	}
};

int main()
{
	[[maybe_unused]] Solution solution;
	return 0;
}
